package leecode

func findFrequentTreeSum(root *TreeNode) []int {
	hashMap := make(map[int]int) //key为和 , value为出现的次数
	//后序遍历,先求和
	var traversal func(node *TreeNode) int
	traversal = func(node *TreeNode) int {
		//递归终止条件
		if node == nil {
			return 0
		}
		left := traversal(node.Left)
		right := traversal(node.Right)
		sum := left + right + node.Val
		hashMap[sum]++
		return sum
	}
	traversal(root)
	//遍历map集合寻找出现最多的次数
	maxCount := 0
	for _, count := range hashMap {
		maxCount = max(maxCount, count)
	}
	//遍历
	var result []int
	for sum, count := range hashMap {
		if count == maxCount {
			result = append(result, sum)
		}
	}
	return result
}
